#ifndef SET_PERMUTE_H
#define SET_PERMUTE_H

#include <vector>
#include <set>
#include <stack>
#include <list>

template<typename T>
class SetPermute
{
public:
  SetPermute();
  void add_set(std::set<T>);
  bool get_next_permutation(std::vector<T> *result);
private:
  bool first_invocation;
  std::list<std::set<T> > permutation_sets;
  std::stack<std::list<std::set<T> > > remaining_stack;
  std::stack<std::vector<T> > completed_stack;
};

template<typename T>
SetPermute<T>::SetPermute()
{
  first_invocation = true;
}

template<typename T>
void SetPermute<T>::add_set(std::set<T> given)
{
  permutation_sets.push_back(given);
}

template<typename T>
bool SetPermute<T>::get_next_permutation(std::vector<T> *result)
{
  if (first_invocation)
    {
      first_invocation = false;
      remaining_stack.push(permutation_sets);
      std::vector<T> empty_completed;
      completed_stack.push(empty_completed);
    }

  while (! remaining_stack.empty())
    {
      std::vector<T> current_completed =  completed_stack.top(); completed_stack.pop();
      std::list<std::set<T> > current_remaining = remaining_stack.top(); remaining_stack.pop();
      
      if (! current_remaining.empty())
        {
          std::set<T> current_set = *(current_remaining.begin());
          current_remaining.erase(current_remaining.begin());
          for(typename std::set<T>::iterator i = current_set.begin();
              i != current_set.end();
              i++)
            {
              std::vector<T> new_completed = current_completed;
              std::list<std::set<T> > new_remaining = current_remaining;
              std::set<T> new_set = current_set;

              new_completed.push_back(*i);

              new_set.erase(*i);
              if (! new_set.empty())
                new_remaining.push_front(new_set);
              
              remaining_stack.push(new_remaining);
              completed_stack.push(new_completed);
            }
        }
      else
        {
          *result = current_completed;
          return true;
        }      
    }
  return false;
}

#endif // SET_PERMUTE_H
